#include <stdio.h>
#include <stdlib.h>

//散列查找
/*
冲突：
通过散列函数确定的位置已经存放了其他元素，陈这种情况为冲突

解决冲突：
1、拉链法
见图拉链法.jpg
 
装填因子 α = 表中记录数/散列表长度
装填因子会直接影响到散列表的查找效率

2、开放地址法
是指可存放新表项的空闲地址既向它的同义词表项开放，也向非同义词开放
① 线性探测法
发生冲突位置，依次往后寻找空闲表项

② 平方探测法
见图 平方探测法.jpg
注：散列表的长度m必须是一个可以表示成 4j + 3 的素数，才能探测到所有位置


③ 伪随机序列法
见图 伪随机序列法.jpg



常见的散列函数

1）除留余数法———— H(key)= key % p
散列表表长为m，取一个不大于m但最接近或等于m的质数p

2）直接定址法一H(key)= key或H(key) = a*key + b
其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情
况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

3）数字分析法
见图 数字分析法.jpg

4）平方取中法
取关键字的平方值的中间几位作为散列地址





*/

int main()
{
    printf("\n\n========================================================================\n\n");

    printf("\n\n========================================================================\n\n");
    return 0;
}